#!/usr/bin/python
# -*- coding: utf-8 -*-
# 1、线性查找（顺序查找）：
# 算法思想：目标元素值挨个与数组元素比较，直达找到目标元素为止。
# 算法优点：实现简单，应用范围广。
# 算法缺点：效率极低，需要一个元素一个元素的比较，最坏情况下需要把数组中的元素都比较一遍。

# 2、二分法：
# 前提是查找的数组为有序数组。相对于线性查找，待查数组项查找范围越大，体现的查找效率就更为显著。

# 3、插值查找算法：
# 原理: 插值查找算法类似于二分查找算法, 不同的是插值查找每次从自适应middle处开始查找, 效率大大提高:
# 插值算法的总体时间复杂度仍然属于O(log(n))级别的。其优点是，对于表内数据量较大，且关键字分布比较均匀的查找表，使用插值算法的平均性能比二分查找要好得多。反之，对于分布极端不均匀的数据，则不适合使用插值算法。

# 4、斐波那契查找
# 斐波那契数列：又称黄金分割数列，指的是这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, …
# 在数学上，斐波那契被递归方法如下定义：F(1) = 1、F(2) = 1、F(N) = F(n-1)+F(n-2)(n >= 2)，该数列越往后，相邻的两个数的比值越趋于黄金比例值（0.618）。
# 斐波那契查找就是在二分法查找的基础上根据斐波那契数列进行分割。
# 斐波那契查找也是二分法查找的优化，也需要提前对数列记性排序。
# 当被查找数列长度为20时，二分法首次查找选择的是数列中第10个元素做参考物，Fibonacci首次查找按照选取的是数列中第13个元素做参考物；
# 如果被查找数列长度为100，二分法首次查找选择的是数列第50个元素做参照物，而斐波那契数首次查找选取的数列中第89个元素做参考物；
# 数列越长，选择参考点的位置差别越大。具体需要根据斐波那契数列的递归方法选取得到。


# 线性查找：
def lineSearch(arr, value):
    index = 0
    for i in range(len(arr)):
        if arr[i] == value:
            print('arr[%d]=' % i, arr[i])
            index += 1
            break
        else:
            index += 1
    print('循环操作次数：', index)


# 二分法查找（折半查找）:非递归
def dichotomySearch(arr, value):
    length = len(arr)
    mid = (length-1)//2
    # print('列表中间位下标', mid)
    min = 0
    max = length-1
    # while True:
    while min < max:
        center = (min+max)//2
        if arr[center] > value:
            max = center-1
        elif arr[center] < value:
            min = center+1
        elif arr[center] == value:
            # 返回在列表的下标
            return center
    return -1


# 二分法查找（折半查找）:递归
def dichotomy(arr, value):
    midIndex = len(arr)//2
    if value > arr[midIndex]:
        dichotomy(arr[midIndex+1:], value)
    elif value < arr[midIndex]:
        dichotomy(arr[0:midIndex], value)
    elif value == arr[midIndex]:
        print(value, 'in the list')


# 插值查找算法：
def interpolation_search(arr, value):
    low = 0
    high = len(arr)-1
    time = 0
    while low < high:
        time += 1
        mid = low + int((high-low)*(value-arr[low])/(arr[high]-arr[low]))
        # print('mid=%s,low=%s,high=%s' % (mid, low, high))
        if value < arr[mid]:
            high = mid-1
        elif value > arr[mid]:
            low = mid+1
        else:
            print('time：', time)
            return mid
    if value == arr[low]:
        return low
    else:
        return -1


# 斐波那契查找
def feibonacci_search(arr, value):
    # 创建一个斐波那契列表,其中最大元素值必须超过所要查找表的元素个数的值
    F = []
    F.append(1)
    F.append(1)
    for i in range(20):
        F.append(F[i]+F[i+1])

    low = 0
    high = len(arr)-1
    # 为了使得查找的表满足斐波那契特性，在表的最后添加几个同样的值，这个值是原查找表的最后元素值
    # 添加的个数由 F[k]-1-high 决定
    k = 0
    while high > F[k]-1:
        k += 1
    # print(k)
    i = high
    while F[k]-1 > i:
        arr.append(arr[high])
        i += 1
    # print('new arr:',arr)
    # 算法逻辑，time表示循环次数
    time = 0
    while low <= high:
        time += 1
        if k < 2:
            mid = low
        else:
            mid = low+F[k-1]-1
        # print(f'low={low},mid={mid},high ={high}')
        # 防止F列表下标溢出，设置if...else
        if value < arr[mid]:
            high = mid-1
            k -= 1
        elif value > arr[mid]:
            low = mid+1
            k -= 2
        else:
            if mid <= high:
                print(f'time={time}')
                return mid
            else:
                print(f'time={time}')
                return high
    print(f'time={time}')
    return None


if __name__ == '__main__':
    arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16, 18,
           19, 24, 45, 63, 105, 269, 330, 369, 400]
    x = 16
    lineSearch(arr, x)

    print('arr[%d] =' % dichotomySearch(arr, x), arr[dichotomySearch(arr, x)])

    dichotomy(arr, x)

    print('arr[%d] =' % interpolation_search(arr, x), arr[interpolation_search(arr, x)])

    print(feibonacci_search(arr, x))
